Ví dụ Sắp xếp nhanh

Trong ví dụ sau đây ta luôn chọn phần tử chốt là phần tử đứng giữa danh sách với chỉ số của phần tử chốt được chọn là k = i n t ( ( k 1 + k 2 ) / 2 ) {\displaystyle k=int((k_{1}+k_{2})/2)}

a = ( 2 , 6 , 3 , 7 , 4 , 5 , 1 ) {\displaystyle a=(2,6,3,7,4,5,1)}

2637451

Do ngẫu nhiên, phần tử chốt a [ 4 ] = 7 {\displaystyle a[4]=7} là phần tử lớn nhất trong dãy, ta tìm từ trái sang phải không có phần tử nào lớn hơn phần tử chốt, do đó ta đổi phần tử chốt với phần tử cuối cùng, danh sách được chia thành hai danh sách con a [ 1..6 ] {\displaystyle a[1..6]} và a [ 7..7 ] {\displaystyle a[7..7]}

263145--7

Việc phân chia tiếp tục với danh sách con a [ 1..6 ] {\displaystyle a[1..6]} . Phần tử chốt được chọn là a[4]=1. Từ trái sang phải tìm được phần tử đầu tiên lớn hơn a [ 4 ] = 1 {\displaystyle a[4]=1} là a [ 1 ] = 2 {\displaystyle a[1]=2} , từ phải sang phần tử đầu tiên <=1 là chính a[4]. Đổi chố hai phần tử này

163245--7

Đi tiếp sang phải ta được a [ 2 ] > 1 {\displaystyle a[2]>1} , ở phía ngược lại đi tiếp sang trái tìm được phần tử nhỏ hơn hoặc bằng chốt là chính a [ 1 ] = 1 {\displaystyle a[1]=1} nhưng lúc này hai đường đã chạm nhau nên ta không đổi nữa. Do vậy a [ 1..6 ] {\displaystyle a[1..6]} được phân chia thành hai danh sách con a [ 1..1 ] {\displaystyle a[1..1]} và a [ 2..6 ] {\displaystyle a[2..6]}

1--63245--7

Tiếp tục phân chia a [ 2..6 ] {\displaystyle a[2..6]} với phần tử chốt a [ 4 ] = {\displaystyle a[4]=} 2 ta được

1--2--3645--7

Tiếp tục phân chia a [ 3..6 ] {\displaystyle a[3..6]} với phần tử chốt a [ 5 ] = 4 {\displaystyle a[5]=4} ta được

1--2--34--65--7

Tiếp tục phân chia a [ 3..4 ] {\displaystyle a[3..4]} với phần tử chốt a [ 4 ] = 4 {\displaystyle a[4]=4} và a [ 5..6 ] {\displaystyle a[5..6]} với phần tử chốt a [ 6 ] = 5 {\displaystyle a[6]=5} ta được

1--2--3--4--5--6--7

Liên quan